package com.javaDemo.ti;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @ClassName: Topk
 * @Auther: csy
 * @Date: 2022/8/9 15:41
 * @Description:
 */
public class Topk {
    public static <Queue> List<Integer> topKByHeap(int[] arr, int k){
        List<Integer> res = new ArrayList<>();
        if(k > arr.length || k == 0){
            return res;
        }
        java.util.Queue<Integer> queue = new PriorityQueue<>();//默认小顶堆
        //Queue<Integer> queue = new PriorityQueue<>((x, y) -> (y - x));//大顶堆

        for (int num : arr){
            if(queue.size() < k){
                queue.add(num);
            }else if(queue.peek() < num){
                queue.poll();
                queue.add(num);
            }
        }
        while (k > 0){
            res.add(queue.poll());
            k--;
        }
        return res;
    }

}
